package com.tim.test.leetcode.simulation.huawei;

import java.util.*;
import java.util.stream.Collectors;

public class Simulation3 {

    public static void main(String[] args) {
        Simulation3 s = new Simulation3();
        Object r=null;
        s.route();// 路由器统计
//        List<List<Integer>> lists = Arrays.asList(Arrays.asList(2,5,6,7,9,5,7),
//                Arrays.asList(1,7,4,3,4));
//        r=s.mergeArr(3,2,lists);
//        r=s.mergeArr();// 数组合并
        System.out.println(r);
    }

    // 路由器统计
    // 构造堆，自定义Comparator；堆pop必为最大值
    public void route(){
        Map<String, MaxHeap.Node> map = new HashMap<>();
        MaxHeap heap = new MaxHeap();

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String str = scanner.nextLine();
            str = str.trim();
            if(str.length()==0){
                continue;
            }
            if(str.matches("\\d+")){
                int size = Integer.valueOf(str);
                List<MaxHeap.Node> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    if(heap.isEmpty()) break;
                    MaxHeap.Node pop = heap.pop();
//                    System.out.println(pop.url);
                    list.add(pop);
                }
                System.out.println(list.stream().map(e->e.url).collect(Collectors.joining(",")));
                list.forEach(heap::push);
            }else{
                if(map.containsKey(str)){
                    MaxHeap.Node node = map.get(str);
                    node.times = node.times+1;
                    heap.adjustUp(node.index);
                }else{
                    MaxHeap.Node node = new MaxHeap.Node(str);
                    node.times=1;
                    heap.push(node);
                    map.put(str, node);
                }
            }

        }

    }

    static class MaxHeap{
        static class Node implements Comparable{
            String url;
            int times;
            int index;
            public Node(String url){
                this.url = url;
            }

            @Override
            public int compareTo(Object o) {
                if(!(o instanceof Node) || o ==null){
                    return -1;
                }
                Node nNode = (Node)o;
                return this.times==nNode.times && this.url.equals(((Node) o).url) ? 0
                        : this.times> nNode.times ? 1
                        : this.times< nNode.times ? -1
                        : Comparator.<String>reverseOrder().compare(this.url, nNode.url);
            }
        }
        private Node[] eles;
        private int usedSize;

        public MaxHeap() {
            init(10);
        }

        private void init(int size) {
            eles = new Node[size];
            usedSize = 0;
        }

        /**
         * 将一棵树调整为大堆的思路
         * 1，每颗子树都应该变成大堆
         * 2，从最后一颗子树开始调整
         * <p>
         * 步骤
         * 1，定义子树父节点p，子节点c
         * 2，在父节点左右两边，找到左右孩子的最大值
         * 3，让左右孩子的最大值，和父节点进行交换
         * 4，迭代调整
         */
        public void createHeap(Node[] arr) {
            init(arr.length);
            for (int i = 0; i < arr.length; i++) {
                // 数组值拷贝给eles
                eles[i] = arr[i];
                usedSize++;
            }
            // 最后一个节点下标arr.length-1；父节点下标：(arr.length-1-1)/2
            for (int parent = (arr.length - 2) / 2; parent >= 0; parent--) {
                // 每次调整的结束位置：不超过数组下标最大值
                adjustDown(parent, usedSize);
            }

        }

        // root父节点索引值，len数组长度
        private void adjustDown(int root, int len) {
            int parent = root;
            int child = 2 * parent + 1;

            while (child < len) {// 存在左子节点，为非叶节点

                // 若右子节点存在；获取子节点最大值
                if (child + 1 < len && eles[child + 1].compareTo(eles[child])>0) {
                    child++;
                }

                if (eles[child].compareTo(eles[parent])>0) {
                    // 子节点最大值大于父节点值，交换
                    swap(eles, child, parent);
                    // 处理交换后子树
                    parent = child;
                    child = 2 * parent + 1;
                } else {
                    break;
                }

            }

        }

        private void swap(Node[] arr, int i, int j) {
            if (i == j) {
                return;
            }
            Node temp = arr[i];
            arr[i] = arr[j];
            arr[i].index = i;
            arr[j] = temp;
            arr[j].index = j;
        }

        public void push(Node val) {
            ensureCapacity();
            eles[usedSize] = val;
            val.index=usedSize;
            usedSize++;
            adjustUp(usedSize - 1);
        }

        private void ensureCapacity() {
            if (eles.length == usedSize) {
                eles = Arrays.copyOf(eles, eles.length * 2);
            }
        }

        // 上浮
        private void adjustUp(int child) {
            int parent = (child - 1) / 2;
            while (child > 0) {
                if (eles[child].compareTo(eles[parent])>0) {
                    // cVal>pVal，交换c、p值；
                    swap(eles, child, parent);
                    // 处理祖级树
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
                    break;
                }
            }
        }

        public Node pop() {
            if (isEmpty()) {
                throw new RuntimeException();
            }
            Node node = eles[0];
            swap(eles, 0, usedSize-1);
            usedSize--;
            // 除顶层树外，顺序均正常；顶层树下沉即可
            adjustDown(0, usedSize);
            return node;
        }

        private boolean isEmpty() {
            return usedSize == 0;
        }

        public Node peek(){
            if (isEmpty()) {
                throw new RuntimeException();
            }
            Node node = eles[0];
            return node;
        }
    }

    // 合并数组
    // 循环；越界则跳过
    public List<Integer> mergeArr(){
        int longth=0, nums=0;
        List<List<Integer>> lists=new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String s = scanner.nextLine();
            if(longth==0){
                longth = Integer.valueOf(s);
                if(longth<1 || longth>=10){
                    throw new RuntimeException();
                }
                continue;
            }
            if(nums==0){
                nums = Integer.valueOf(s);
                if(nums<1 || nums>=1000){
                    throw new RuntimeException();
                }
                continue;
            }
            s = s.trim();
            if(s.length()==0){
                continue;
            }
            List<Integer> list = Arrays.stream(s.split(","))
                    .map(Integer::valueOf)
                    .collect(Collectors.toList());
            lists.add(list);
            if(lists.size()==nums){
                break;
            }
        }
        return mergeArr(longth, nums, lists);
    }

    public List<Integer> mergeArr(int size, int nums, List<List<Integer>> lists){
        if(nums!=lists.size()){
            return null;
        }

        final Integer totalSize = lists.stream().map(List::size).reduce(Integer::sum).get();
        List<Integer> result = new ArrayList<>(totalSize);
        int times = 0;
        Set<Integer> skipSet = new HashSet<>();
        while(skipSet.size()!=lists.size()){
            final int startIndex = times * size;
            times++;
            final int endIndex = times * size;
            for (int i = 0; i < lists.size(); i++) {
                if(skipSet.contains(i)){
                    continue;
                }
                final List<Integer> list = lists.get(i);
                if(list.size()> startIndex){
                    for (int j = startIndex; j<list.size()&&j < endIndex; j++) {
                        result.add(list.get(j));
                    }
                }else{
                    skipSet.add(i);
                }
            }
        }

        return result;
    }


}
